# -*- coding: utf-8 -*-
# @File    : test_121.py
# @Date    :  2025-07-28 16:17
# @Author  : zoey1
from typing import List


class Solution:
    """
    面试经典150题-[数组/字符串]-121. 买卖股票的最佳时机
    给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
    你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
    返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
    """

    def maxProfit(self, prices: List[int]) -> int:
        """
        初始解法
        判定结果：时间复杂度太高，list太大的话，性能很差
        """
        buy_day = None
        sell_day = None
        # 初始化变量为负无穷
        max_price_change = float('-inf')
        for i in range(prices.__len__()):
            for j in range(i + 1, prices.__len__()):
                change_price = - (prices[i] - prices[j])
                if change_price > max_price_change:
                    max_price_change = change_price
                    buy_day = i
                    sell_day = j
        if max_price_change < 0:
            max_price_change = 0
        print('max_price_change:', max_price_change, 'buy_day:', buy_day, 'sell_day:', sell_day)
        return max_price_change

    def maxProfit_2(self, prices: List[int]) -> int:
        """
        解题思路：双指针
        1、前后的价格去对比，如果前面的价格大于后面的价格，那这天的买入对未来来说，肯定跟“最大收益”无关，尽可能找到最低价
        2、然后，根据找定的最低价（相对前面的价格来说），去计算未来哪天涨的最多，计算“最大收益”
        """
        left = 0
        # 初始化变量为负无穷
        max_price_change = float('-inf')
        buy_day = None
        sell_day = None
        for right in range(1, len(prices)):
            if prices[left] > prices[right]:
                left = right
            else:
                price_change = prices[right] - prices[left]
                if price_change > max_price_change:
                    max_price_change = price_change
                    buy_day = left
                    sell_day = right
        if max_price_change < 0:
            max_price_change = 0
        print('max_price_change:', max_price_change, 'buy_day:', buy_day, 'sell_day:', sell_day)
        return max_price_change

    def maxProfit_review_20250731(self, prices: List[int]) -> int:
        """
        跟题目【面试经典150题-[数组/字符串]-121. 买卖股票的最佳时机】非常容易混淆
        解题思路：
        找到相对最低价，找到每个相对最低价的能是利润最大化的卖出价格。每个相对的也会进行比较，从而找到利润最大化
        """
        buy = prices[0]
        sell = float('-inf')
        max_profit = 0
        for price in prices:
            if price < buy:
                buy = price
            elif (price - buy) > max_profit:
                sell = price
                max_profit = sell - buy
        print(max_profit)
        return max_profit

    def maxProfit_review_20250802(self, prices: List[int]) -> int:
        """
        解题思路：枚举法，维护买入的最小值；再更新找到卖出的最大值
        """
        max_profit = 0
        buy = prices[0]
        sell = 0
        for price in prices:
            if price < buy:
                buy = price
            elif price-buy > max_profit:
                sell = price
                max_profit = sell - buy
        return max_profit


if __name__ == '__main__':
    s = Solution()
    # prices = [7, 6, 4, 3, 1]
    # prices = [7, 1, 5, 3, 6, 4]
    prices = [7, 3, 6, 1, 5, 4]
    # s.maxProfit_2(prices)
    s.maxProfit_review_20250731(prices)
